package algorithm.advance;

import java.util.HashMap;

public class RodCut {
	private static RodCut rodCut = new RodCut();
	
	public static void main(String[] args){
		
		int[] a = {0,1,5,8,9,10,17,17,20,24,30,1,5,8,9,10,17,17,20,24,30,1,5,8,9,10,17,17,20,24,30,1,5,8,9,10,17,17,20,24,30,1,5,8,9,10,17,17,20,24,30,1,5,8,9,10,17,17,20,24,30};
		int[] c = new int[100]; 
		
		long time = System.currentTimeMillis();
		//System.out.println(RodCut.getInstance().badMethod(a,30));
		//System.out.println(System.currentTimeMillis() - time);
		//time = System.currentTimeMillis();
		//System.out.println(RodCut.getInstance().memoMethod(a, 60, c));
		//System.out.println(System.currentTimeMillis() - time);
		//time = System.currentTimeMillis();
		//System.out.println(RodCut.getInstance().bottomUpMethod(a, 60));
		//System.out.println(System.currentTimeMillis() - time);
		
		ResultCut result = RodCut.getInstance().extendBottomUpMethod(a, 8);
		int n = 8;
		int[] s = result.getS();
		while(n > 0){
			System.out.print(s[n] + " ");
			n = n - s[n];
		}
	}
	public static RodCut getInstance(){
		return rodCut;
	}
	public int badMethod(int[] a,int n){
		if(n == 0){
			return 0;
		}
		int q = -10;
		for(int i = 1; i <= n; i++){
			q = Math.max(q, a[i] + badMethod(a,n - i));
		}
		return q;
	}
	public int memoMethod(int[] a,int n,int[] c){
		if(n == 0){
			return 0;
		}
		if(c[n] != 0){
			return c[n];
		}
		
		int q = -10;
		for(int i = 1; i <= n; i++){
			q = Math.max(q, a[i] + memoMethod(a,n - i,c));
		}
		c[n] = q;
		return q;
	}
	
	public int bottomUpMethod(int[] a,int n){
		int q = -1;
		int[] r = new int[100];
		for(int j = 1; j <= n; j++){
			for(int i = 1; i <= j; i++){
				q = Math.max(q, a[i] + r[j - i]);
			}
			r[j] = q;
		}
		return r[n];
	}
	
	public ResultCut extendBottomUpMethod(int[] a,int n){
		ResultCut result = new ResultCut();
		int q = -1;
		int[] r = new int[100];
		for(int j = 1; j <= n; j++){
			for(int i = 1; i <= j; i++){
				if(q < a[i] + r[j - i]){
					q = a[i] + r[j - i];
					int[] c = result.getS();
					if(j == 6){
						int b;
						b = 6;
					}
					
					c[j] = i;
				}
			}
			r[j] = q;
		}
		result.setQ(r[n]);
		return result;
	}
	
	 static class ResultCut{
		 private int[] s = new int[100];
		 private int q =0;
		 public int[] getS() {
			return s;
		 }
		 public void setS(int[] s) {
			this.s = s;
		 }
		 public int getQ() {
			return q;
		 }
		 public void setQ(int q) {
			this.q = q;
		 }
	 }
	
}
